package cn.yoaket.algorithm;

import cn.yoaket.unit.Edge;
import cn.yoaket.unit.Point;

import java.nio.file.Path;
import java.util.*;

public class Dijkstra {
    private static final int M = 10000;


    static Point[] init(List<Edge> edges){
        Set<Point> vertex = new HashSet<>();

        int count = 0;
        for (Edge edge : edges) {
            if(!vertex.contains(edge.begin())) {
                edge.begin().setId(count++);
                vertex.add(edge.begin());
            }
            if(!vertex.contains(edge.end())){
                edge.end().setId(count++);
                vertex.add(edge.end());
            }
        }

        for (Point point : vertex) {
            for (Edge edge : edges) {
                if(point.equals(edge.begin()))
                    edge.begin().setId(point.getId());
                if(point.equals(edge.end()))
                    edge.end().setId(point.getId());
            }
        }

        Point[] mapping = new Point[vertex.size()];

        for (Point point : vertex) {
            mapping[point.getId()] = point;
        }
        return mapping;
    }

    static double [][] createGraph(List<Edge> edges,int size){
        double[][] matrix = new double[size][size];
        //初始化邻接矩阵
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                matrix[i][j] = M;
            }
        }
        for (Edge edge : edges) {
            matrix[edge.begin().getId()][edge.end().getId()] = edge.length()*(1-edge.getRatio());
            matrix[edge.end().getId()][edge.begin().getId()] = edge.length()*(1-edge.getRatio());
        }
        return matrix;
    }

    static List<Point> getEdge(Point begin,Point end,List<Edge> edges){
        for (Edge edge : edges) {
            if(edge.begin().equals(begin) && edge.end().equals(end))
                return edge.vertexes();
            else if(edge.begin().equals(end) && edge.end().equals(begin)){
                Collections.reverse(edge.vertexes());
                return edge.vertexes();
            }
        }
        return new ArrayList<>();
    }

    public static Edge execute(Point begin, Point end,List<Edge> edges) {

        Point start = nearest(begin,edges);
        Point goal = nearest(end,edges);


        // 二维数组每一行分别是 A、B、C、D、E 各点到其余点的距离,
        // A -> A 距离为0, 常量M 为正无穷

        Point[] mapping =  init(edges);

        int size = mapping.length;

        double[][] weight = createGraph(edges,size);

        String[] shortPath = dijkstra(weight, start.getId());

        String[] path = shortPath[goal.getId()].split(",");

        List<Point> vertex = new ArrayList<>();

        for (String s : path) {
            vertex.add(mapping[Integer.parseInt(s)]);
        }

        Edge edge = new Edge();
        edge.add(begin);
        for(int i = 0;i<vertex.size()-1;++i){
            edge.add(getEdge(vertex.get(i),vertex.get(i+1),edges));
        }
        edge.add(end);

        return edge.size()>2?edge:new Edge();
    }

    private static String[] dijkstra(double[][] weight, int start) {
        // 接受一个有向图的权重矩阵，和一个起点编号start（从0编号，顶点存在数组中）
        // 返回一个int[] 数组，表示从start到它的最短路径长度
        // 顶点个数
        int n = weight.length;
        // 保存start到其他各点的最短路径
        //double[] shortPath = new double[n];
        // 保存start到其他各点最短路径的字符串表示
        String[] path = new String[n];
        for (int i = 0; i < n; i++) {
            path[i] = start + "," + i;
        }
        // 标记当前该顶点的最短路径是否已经求出,1表示已求出
        int[] visited = new int[n];

        // 初始化，第一个顶点已经求出
        //shortPath[start] = 0;
        visited[start] = 1;

        // 要加入n-1个顶点
        for (int count = 1; count < n; count++) {
            // 选出一个距离初始顶点start最近的未标记顶点
            int k = -1;
            double dmin = Integer.MAX_VALUE;
            for (int i = 0; i < n; i++) {
                if (visited[i] == 0 && weight[start][i] < dmin) {
                    dmin = weight[start][i];
                    k = i;
                }
            }

            // 将新选出的顶点标记为已求出最短路径，且到start的最短路径就是dmin
            //shortPath[k] = dmin;
            visited[k] = 1;

            // 以k为中间点，修正从start到未访问各点的距离
            for (int i = 0; i < n; i++) {
                //如果 '起始点到当前点距离' + '当前点到某点距离' < '起始点到某点距离', 则更新
                if (visited[i] == 0 && weight[start][k] + weight[k][i] < weight[start][i]) {
                    weight[start][i] = weight[start][k] + weight[k][i];
                    path[i] = path[k] + "," + i;
                }
            }
        }
        return path;
    }


    static double dis(Point a,Point b){
        return Math.sqrt(Math.pow(a.getX() - b.getX(),2)+Math.pow(a.getY() - b.getY(),2));
    }

    static Point nearest(Point local,List<Edge> edges){
        Point near = edges.get(0).begin();
        for (Edge edge : edges) {
            if(dis(edge.end(),local)<dis(local,near))
                near = edge.end();
            if(dis(edge.begin(),local)<dis(local,near))
                near = edge.begin();
        }
        return near;
    }
}
